/**
 * 
 */
package edu.umd.clip.lm.model.decoding;

import edu.umd.clip.lm.factors.*;
import edu.umd.clip.lm.factors.Dictionary;
import edu.umd.clip.lm.model.*;
import edu.umd.clip.lm.model.data.Context;
import edu.umd.clip.lm.model.decoding.DecodingContext.ItemData;
import edu.umd.clip.lm.model.decoding.FuturePredictions.FuturePrediction;
import edu.umd.clip.lm.model.decoding.FuturePredictions.PredictionKey;
import edu.umd.clip.lm.util.tree.*;
import edu.umd.clip.lm.questions.*;
import edu.umd.clip.lm.util.*;
import edu.umd.clip.lm.storage.*;
import edu.umd.clip.lm.storage.AbstractProbTreeStorage.Key;

import java.util.*;
import java.util.concurrent.atomic.AtomicLong;
/**
 * @author Denis Filimonov <den@cs.umd.edu>
 *
 */
public class Decoder {
	public static class TimingData {
		/**
		 * 
		 */
		private long totalPrologTime;
		/**
		 * 
		 */
		private long totalPartitionTime;
		/**
		 * 
		 */
		private long totalMergeTime;
		/**
		 * 
		 */
		private long totalStorageTime;
		/**
		 * 
		 */
		private long totalTreeMergingTime;
		private static AtomicLong totalProbTreeRequestCount = new AtomicLong();
		private static AtomicLong totalProbTreeRequestTime = new AtomicLong();
		private static AtomicLong totalPrePartitionTime = new AtomicLong();
		private static AtomicLong totalSplittingCount = new AtomicLong();
		private static AtomicLong totalSplittingTime = new AtomicLong();
		private static AtomicLong totalCuttingCount = new AtomicLong();
		private static AtomicLong totalCuttingTime = new AtomicLong();
		private static AtomicLong totalQuestionTime = new AtomicLong();
		private static AtomicLong totalPredictionTime = new AtomicLong();
		private static AtomicLong totalQuestionCount = new AtomicLong();
		private static AtomicLong totalFwdSplittingTime = new AtomicLong();
		
		/**
		 * 
		 */
		public TimingData(long totalPrologTime, long totalPartitionTime,
				long totalMergeTime, long totalStorageTime,
				long totalTreeMergingTime) {
			this.totalPrologTime = totalPrologTime;
			this.totalPartitionTime = totalPartitionTime;
			this.totalMergeTime = totalMergeTime;
			this.totalStorageTime = totalStorageTime;
			this.totalTreeMergingTime = totalTreeMergingTime;
		}

		/**
		 * @return the totalPrologTime
		 */
		public long getTotalPrologTime() {
			return totalPrologTime;
		}

		/**
		 * @param totalPrologTime the totalPrologTime to set
		 */
		public void setTotalPrologTime(long totalPrologTime) {
			this.totalPrologTime = totalPrologTime;
		}

		/**
		 * @return the totalPartitionTime
		 */
		public long getTotalPartitionTime() {
			return totalPartitionTime;
		}

		/**
		 * @param totalPartitionTime the totalPartitionTime to set
		 */
		public void setTotalPartitionTime(long totalPartitionTime) {
			this.totalPartitionTime = totalPartitionTime;
		}

		/**
		 * @return the totalMergeTime
		 */
		public long getTotalMergeTime() {
			return totalMergeTime;
		}

		/**
		 * @param totalMergeTime the totalMergeTime to set
		 */
		public void setTotalMergeTime(long totalMergeTime) {
			this.totalMergeTime = totalMergeTime;
		}

		/**
		 * @return the totalStorageTime
		 */
		public long getTotalStorageTime() {
			return totalStorageTime;
		}

		/**
		 * @param totalStorageTime the totalStorageTime to set
		 */
		public void setTotalStorageTime(long totalStorageTime) {
			this.totalStorageTime = totalStorageTime;
		}

		/**
		 * @return the totalTreeMergingTime
		 */
		public long getTotalTreeMergingTime() {
			return totalTreeMergingTime;
		}

		/**
		 * @param totalTreeMergingTime the totalTreeMergingTime to set
		 */
		public void setTotalTreeMergingTime(long totalTreeMergingTime) {
			this.totalTreeMergingTime = totalTreeMergingTime;
		}
	}

	protected int debug = 0;
	protected static int DEBUG = 0;
	
	private ForestModel forest;
	private LanguageModel[] lms;
	
	private double PRUNING_THRESHOLD = 1E-6; 
	
	private boolean useGhosts = true;
	//private boolean useBackoff = true;
	
	private AbstractProbTreeStorage storage;
	
	//private final static boolean USE_CUMULATIVE_BACKOFF = false;
	
	public Decoder(ForestModel forest) {
		this.forest = forest;
		init();
	}
	
	public Decoder(ForestModel forest, int cacheSize) {
		this.forest = forest;
		init();
	}
 
	private void init() {
		lms = forest.getModels().toArray(new LanguageModel[forest.getModels().size()]);
		
		Experiment experiment = Experiment.getInstance(); 
		debug = experiment.getDebugDecoder();
		DEBUG = debug;
		
		if (DecoderCompactProbTree.getEmptyTree() == null) {
			DecoderCompactProbTree emptyTree = DecoderCompactProbTree.constructEmptyTree(experiment.getHFT().getTree());
			DecoderCompactProbTree.setEmptyTree(emptyTree);
		}
	}

	public SentenceContext addWord(SentenceContext ctx, long overtFactors) {
		return ctx.addWord(overtFactors);
	}

	public void debugContext(DecodingContext context, StringBuilder sb) {
		TreeTrellisNode currentNode = context.getCurrentNode();
		double prob = currentNode.getTotalProb();
		double oldProb = currentNode.getPreviousNode().getTotalProb();
		
		double logProb = Math.log10(prob) + currentNode.getCumulativeLogScale();
		double logPrevProb = Math.log10(oldProb) + currentNode.getPreviousNode().getCumulativeLogScale();
		
		double logDiff = Math.log10(prob / oldProb) + currentNode.getLogScale();
		
		int totalPrevLinks = 0;
		int maxPrevLinks = 0;
		
		for(TrellisNodeItem item : currentNode.items.keySet()) {
			int prevLinksCount = item.getPrevItems() == null ? 0 : item.getPrevItems().size();
			totalPrevLinks += prevLinksCount;
			if (prevLinksCount > maxPrevLinks) {
				maxPrevLinks = prevLinksCount;
			}
		}
		
		sb.append(String.format("Current Word: %s, Items: [%d] - %d, [%d] - %d, backlinks: maxPrev=%d, totalPrev=%d, prob = %g, prevProb = %g, diff = %g [%g]\n",
				FactorTuple.toStringNoNull(currentNode.currentWord),
				currentNode.getPreviousNode().time,
				currentNode.getPreviousNode().isHead() ? 0 : currentNode.getPreviousNode().items.size(),
				currentNode.time,
				currentNode.items.size(),
				maxPrevLinks,
				totalPrevLinks,
				logProb,
				logPrevProb,
				Math.pow(10.0, logDiff),
				logDiff));
	}
	
	public void debugContext(SentenceContext ctx) {
		double prob = ctx.getCurrentSlice().getTotalProb();
		double oldProb = ctx.getSliceByOffset(-1).getTotalProb();
		if (prob < 0 || oldProb < 0) {
			System.err.printf("prob=%g, oldProb=%g\n", prob, oldProb);
		}
		double logProb = ctx.getLogProb();
		double logDiff = Math.log10(prob / oldProb) + ctx.getCurrentSlice().getSliceLogScale();
		int totalPrevLinks = 0;
		int maxPrevLinks = 0;
		
		for(ArrayList<TrellisItem> prevs : ctx.getCurrentSlice().getPrevious().curr2prev.values()) {
			if (prevs != null) {
				if (prevs.size() > maxPrevLinks) maxPrevLinks = prevs.size();
				totalPrevLinks += prevs.size();
			}
		}
		System.out.printf("Current Word: %s, Items: [%d] - %d, [%d] - %d, backlinks: maxPrev=%d, totalPrev=%d, prob = %g, diff = %g [%g]\n",
				FactorTuple.toStringNoNull(ctx.getCurrentSlice().getOvertFactors()),
				ctx.getCurrentSlice().getPrevious().getTime(),
				ctx.getCurrentSlice().getPrevious().numItems(),
				ctx.getCurrentSlice().getTime(),
				ctx.getCurrentSlice().numItems(),
				maxPrevLinks,
				totalPrevLinks,
				logProb,
				Math.pow(10.0, logDiff),
				logDiff);
	}
	
	public double evaluateSentence(long[] sentence) {
		return evaluateSentence(sentence, false);
	}
	
	public double evaluateSentence(long[] sentence, boolean useConstraints) {
		ArrayList<FactorTuple> tuples = new ArrayList<FactorTuple>(sentence.length);
		for(long tuple : sentence) {
			tuples.add(new FactorTuple(tuple));
		}
		return evaluateSentence(tuples, useConstraints);
	}
	
	public double evaluateSentence(Collection<FactorTuple> sentence, boolean useConstraints) {
		SentenceContext ctx = createContext();
		final FactorTupleDescription desc = Experiment.getInstance().getTupleDescription(); 
		final long overtMask = desc.getOvertFactorsMask();
		for(FactorTuple tuple : sentence) {
			long constraints = tuple.getBits() & desc.getHiddenFactorsMask();
			tuple = new FactorTuple(tuple.getBits() & overtMask);
			ctx = ctx.addWord(tuple.getBits());
			partition(ctx);
			ctx.setLastSliceTotalProb(ctx.getCurrentSlice().getTotalProb());
			if (useConstraints && constraints != 0) {
				applyConstraint(ctx, constraints);
			}
			if (debug > 0) {
				debugContext(ctx);
				
				if (debug > 1) {
					ctx.getTrellis().dumpTrellis(String.format("trellis-%d-%s.dot", 
							ctx.getTrellis().getCurrentSlice().getTime(), tuple.toStringNoNull().replace('/', ' ')));
				}
			}
			if (useGhosts) {
				if (ctx.getCurrentSlice().getTime() > forest.getOrder()+1) {
					ctx.getSliceByOffset(- (forest.getOrder() + 1)).makeGhost();
				}
			}
			//assert(ctx.getCurrentSlice().checkLinks());
		}
		return ctx.getLogProb();
	}
	
	public double newEvaluateSentence(long[] sentence, boolean useConstraints) {
		TreeTrellisNode currentNode = createTreeTrellis(forest.getOrder() - 1);
		return newEvaluateSentence(currentNode, sentence, useConstraints);
	}
	
	public double newEvaluateSentence(TreeTrellisNode currentNode, long[] sentence, boolean useConstraints) {
		final FactorTupleDescription desc = Experiment.getInstance().getTupleDescription();
		final long overtFactorsMask = desc.getOvertFactorsMask();
		final long hiddenFactorsMask = desc.getHiddenFactorsMask();
		
		final int lockNodes = /*forest.getOrder() +*/ 2;
		
		double prob = 1.0;
		
		// skip possible <s> in the beginning
		int i=0;
		while(i < sentence.length && Dictionary.isStart(FactorTuple.getValue(sentence[i],desc.getMainFactorIndex()))) {
			++i;
		}
		
		for(; i<sentence.length; ++i) {
			long word = sentence[i] & overtFactorsMask;
			long constraints = sentence[i] & hiddenFactorsMask;
			
			currentNode = currentNode.appendNodeAndLock(word);
			TreeTrellisNode prevNode = currentNode.getPreviousNode();
			try {
				if (!currentNode.isDecoded()) {
					prevNode.lock(forest.getOrder());
					try {
						DecodingContext context = new DecodingContext(currentNode, forest);
						
						partition(context);
						
						if (useConstraints && constraints != 0) {
							applyConstraint(currentNode, constraints);
						}
						
						currentNode.finishDecoding();
					} finally {
						prevNode.unlock(forest.getOrder());
					}
				}
	
				prob = currentNode.getCumulativeLogScale() + Math.log10(currentNode.getTotalProb());
			} finally {
				currentNode.unlock();
			}
		}
		currentNode.releasePath();
		
		return prob;
	}
	
	private void applyConstraint(TreeTrellisNode node, long constraint) {
		// first, express the constraint in the form of a binary prefix
		BinaryPrefix thePrefix = null;
		final int hiddenFactors[] = FactorTuple.getHiddenValues(constraint);
		
		Map<FactorTuple, BinaryPrefix> binaryPrefixes = Experiment.getInstance().getHiddenPrefixes();
		
		for(Map.Entry<FactorTuple, BinaryPrefix> entry : binaryPrefixes.entrySet()) {
			int hidFactors[] = entry.getKey().getHiddenValues();
			boolean matched = true;
			for(byte i = 0; i < hiddenFactors.length; ++i) {
				if (hiddenFactors[i] != Dictionary.getNull() && hiddenFactors[i] != hidFactors[i]) {
					matched = false;
					break;
				}
			}
			if (matched) {
				BinaryPrefix prefix = entry.getValue();
				//System.err.printf("(%s) %s matched\n", entry.getKey().toStringNoNull(), prefix);
				if (thePrefix == null) {
					thePrefix = prefix;
				} else {
					thePrefix = BinaryPrefix.getCommonPrefix(thePrefix, prefix);
				}
			}
		}
		
		if (thePrefix == null || thePrefix.getSize() == 0) {
			System.err.println("Hidden factors:" + Arrays.toString(hiddenFactors));
			System.err.printf("Can't find a common prefix for %s\n", FactorTuple.toStringNoNull(constraint));
			return;
		}
		
		HashSet<TrellisNodeItem> itemsToRemove = new HashSet<TrellisNodeItem>();
		
		for(TrellisNodeItem item : node.items.keySet()) {
			ProbTree probTree = item.tree;
			@SuppressWarnings("unused")
			double totalProb = probTree.getTotalProb();
			
			ProbTree cutProbTree = probTree.cut(thePrefix);
			if (probTree == cutProbTree) {
				// the constraint is fully matched
				//System.err.printf("item %s fully matched the constraint %s\n", item, thePrefix);
				continue;
			}
			if (cutProbTree == null) {
				// not matched, remove the item
				itemsToRemove.add(item);
				continue;
			}
			// re-scale the remainder
			//System.err.printf("rescaling item %s by %g\n", item.toString(), totalProb / cutProbTree.getTotalProb());
			// do not re-scale (this way we compute joint probability, as opposed to conditional) 
			//cutProbTree.scale(totalProb / cutProbTree.getTotalProb());
			
			item.tree = cutProbTree;
		}
		if (itemsToRemove.size() > 0) {
			System.err.printf("removing %d items due to constraints\n", itemsToRemove.size());
			for(TrellisNodeItem item : itemsToRemove) {
				node.removeItem(item);
			}
		}

	}
	
	private void applyConstraint(SentenceContext ctx, long constraint) {
		// first, express the constraint in the form of a binary prefix
		BinaryPrefix thePrefix = null;
		final int hiddenFactors[] = FactorTuple.getHiddenValues(constraint);
		
		Map<FactorTuple, BinaryPrefix> binaryPrefixes = Experiment.getInstance().getHiddenPrefixes();
		
		for(Map.Entry<FactorTuple, BinaryPrefix> entry : binaryPrefixes.entrySet()) {
			int hidFactors[] = entry.getKey().getHiddenValues();
			boolean matched = true;
			for(byte i = 0; i < hiddenFactors.length; ++i) {
				if (hiddenFactors[i] != Dictionary.getNull() && hiddenFactors[i] != hidFactors[i]) {
					matched = false;
					break;
				}
			}
			if (matched) {
				BinaryPrefix prefix = entry.getValue();
				//System.err.printf("(%s) %s matched\n", entry.getKey().toStringNoNull(), prefix);
				if (thePrefix == null) {
					thePrefix = prefix;
				} else {
					thePrefix = BinaryPrefix.getCommonPrefix(thePrefix, prefix);
				}
			}
		}
		
		if (thePrefix == null || thePrefix.getSize() == 0) {
			System.err.println("Hidden factors:" + Arrays.toString(hiddenFactors));
			System.err.printf("Can't find a common prefix for %s\n", FactorTuple.toStringNoNull(constraint));
			return;
		}
		
		HashSet<TrellisItem> itemsToRemove = new HashSet<TrellisItem>();
		
		for(TrellisItem item : ctx.getCurrentSlice().getElements()) {
			ProbTree probTree = item.getProbTree();
			@SuppressWarnings("unused")
			double totalProb = probTree.getTotalProb();
			
			ProbTree cutProbTree = probTree.cut(thePrefix);
			if (probTree == cutProbTree) {
				// the constraint is fully matched
				//System.err.printf("item %s fully matched the constraint %s\n", item, thePrefix);
				continue;
			}
			if (cutProbTree == null) {
				// not matched, remove the item
				itemsToRemove.add(item);
				continue;
			}
			// re-scale the remainder
			//System.err.printf("rescaling item %s by %g\n", item.toString(), totalProb / cutProbTree.getTotalProb());
			// do not re-scale (this way we compute joint probability, as opposed to conditional) 
			//cutProbTree.scale(totalProb / cutProbTree.getTotalProb());
			
			item.tree = cutProbTree;
		}
		if (itemsToRemove.size() > 0) {
			System.err.printf("removing %d items due to constraints\n", itemsToRemove.size());
			ctx.getCurrentSlice().removeNodes(itemsToRemove);
		}
	}
	
	private void newGeneratePredictions(DecodingContext context) {
		//final int lmSequence[] = Experiment.getInstance().getLmIdSequence(forest);
		FuturePredictions<TrellisNodeItem> predictions = context.getPredictions();
		long overtFactors = context.getFutureWord();

		Map<Key,OnDiskCompactProbTree> allProbTrees;
		{
			RequestBundle<Key, OnDiskCompactProbTree> currentRequests = context.getCurrentRequests();
			try {
				currentRequests.sync();
			} catch(InterruptedException e) {
				e.printStackTrace();
			}
			allProbTrees = currentRequests.getResults();
		}
		
		TreeTrellisNode theNode = context.getCurrentNode();
		
		for(Map.Entry<PredictionKey, FuturePrediction<TrellisNodeItem>> entry : predictions.getPredictions().entrySet()) {
			PredictionKey key = entry.getKey();
			FuturePrediction<TrellisNodeItem> prediction = entry.getValue();
			
			OnDiskCompactProbTree probTree = computeProbTree(key.nodes, overtFactors, allProbTrees, null);
			
			if (probTree != null) {
				probTree.normalize();
				TrellisNodeItem item = new TrellisNodeItem(ProbTree.makeProbTreeNew(probTree), 0, theNode.time);
				
				ArrayList<TrellisNodeItem> prevLinks = prediction.getPrevLinks();
				
				if (prevLinks.isEmpty()) {
					// unigram model doesn't have any context
					assert(forest.getOrder() == 1);
					item.setPrevProb(theNode.getPreviousNode().getTotalProb());
				} else {
					for(TrellisNodeItem i : prevLinks) {
						item.addPrevItem(i);
					}
					for(TrellisNodeItem prevItem : prevLinks) {
						item.addPrevProb(prevItem.getProb());
						prevItem.addNextItem(item);
					}
				}
				theNode.insertItem(item);
			}
		}
	}

	private void generatePredictions(SentenceContext ctx, TrellisSlice slice) {
		//final int lmSequence[] = Experiment.getInstance().getLmIdSequence(forest);
		FuturePredictions<TrellisItem> predictions = slice.getPredictions();
		long overtFactors = slice.getOvertFactors();

		Map<Key,OnDiskCompactProbTree> allProbTrees;
		{
			RequestBundle<Key, OnDiskCompactProbTree> currentRequests = ctx.getCurrentRequests();
			try {
				currentRequests.sync();
			} catch(InterruptedException e) {
				e.printStackTrace();
			}
			allProbTrees = currentRequests.getResults();
		}
		
		
		for(Map.Entry<PredictionKey, FuturePrediction<TrellisItem>> entry : predictions.getPredictions().entrySet()) {
			PredictionKey key = entry.getKey();
			FuturePrediction<TrellisItem> prediction = entry.getValue();
			ClusterId clusterID = new ClusterId();
			
			OnDiskCompactProbTree probTree = computeProbTree(key.nodes, overtFactors, allProbTrees, clusterID);
			
			if (probTree != null) {
				probTree.normalize();
				
				ArrayList<TrellisItem> prevLinks = prediction.getPrevLinks();
				
				//SliceItem item = new SliceItem(ProbTree.makeProbTree(probTree).compact(), 0, clusterID);
				TrellisItem item = new TrellisItem(ProbTree.makeProbTreeNew(probTree), 0, clusterID);
				
				slice.curr2prev.put(item, prevLinks);
				
				for(TrellisItem prevItem : prevLinks) {
					item.addPrevProb(prevItem.getPrevProb() * prevItem.tree.getTotalProb());
					ArrayList<TrellisItem> lst = slice.prev2curr.get(prevItem);
					if (lst == null) {
						lst = new ArrayList<TrellisItem>(2);
						slice.prev2curr.put(prevItem, lst);
					}
					lst.add(item);
				}
				slice.insertItem(item);
			}
		}
		slice.clearPredictions();
	}
	
	public OnDiskCompactProbTree computeProbTree(BinaryTree<HistoryTreePayload> nodes[], 
			long overtFactors, Map<Key,OnDiskCompactProbTree> allProbTrees, ClusterId clusterID) 
	{
		StringBuilder debugOut = null;
		
		if (debug > 1) {
			debugOut = new StringBuilder('[');
		}
		
		int numTrees = 0;
		OnDiskCompactProbTree probTrees[] = new OnDiskCompactProbTree[nodes.length];
		double treeWeights[] = new double[nodes.length];
		
		double totalWeight = 0.0;
		for(int lmNum=0; lmNum<lms.length; ++lmNum) {
			LanguageModel lm = lms[lmNum];
			double weights[] = forest.getDecodingRuntime().getWeights(lmNum);
			
			int lmid = lm.getIdNum();
			
			BinaryTree<HistoryTreePayload> node = nodes[lmid];
			if (node == null) continue;
			int clusterid = node.getPayload().clusterid;
			
			if (clusterID != null) {
				clusterID.setId(lmid, clusterid);
			}
			
			//LanguageModel currentLM = Experiment.getInstance().getLmByNumId(lmid);
			//Decoder decoder = currentLM.getDecoder();

			if (node.getPayload().isBackoff) {
				if (forest.isBackoffLeavesUseGrandparent()) {
					// a backoff cluster, take the grandparent for interpolation
					BinaryTree<HistoryTreePayload> grandparent = node.getParent().getParent();

					Key storageKey = new Key(lm.getIdNum(), grandparent.getPayload().clusterid, overtFactors);
					OnDiskCompactProbTree gpProbTree = allProbTrees.get(storageKey);
					
					if (gpProbTree == null && !allProbTrees.containsKey(storageKey)) {
						System.err.println("bad key (backoff)");
					}
					//ProbTree gpProbTree = decoder.getInterpolatedProbTree(grandparent, overtFactors);
					double gpBackoff = weights[grandparent.getPayload().clusterid];
					
					if (gpProbTree != null && gpProbTree.getScale() > 0) {
						treeWeights[numTrees] = gpBackoff;
						//gpProbTree = (OnDiskCompactProbTree) gpProbTree.clone();
						//gpProbTree.scale(gpBackoff);
						probTrees[numTrees] = gpProbTree;
						++numTrees;
						totalWeight += gpBackoff;
					}
				}
			} else {
				Key storageKey = new Key(lm.getIdNum(), node.getPayload().clusterid, overtFactors);
				OnDiskCompactProbTree probTree = allProbTrees.get(storageKey);
				//ProbTree probTree = decoder.getInterpolatedProbTree(node, slice.getOvertFactors().getBits());
				if (probTree == null && !allProbTrees.containsKey(storageKey)) {
					System.err.println("bad key");
				}

				double boWeight = weights[clusterid];
				
				if (probTree != null && probTree.getScale() > 0) {
					//if (boWeight != 1.0) {
					//	probTree = (OnDiskCompactProbTree) probTree.clone();
					//	probTree.scale(boWeight);
					//}
					treeWeights[numTrees] = boWeight;
					probTrees[numTrees] = probTree;
					++numTrees;
					totalWeight += boWeight;
				}
			}
		}
		if (debug > 2 && clusterID != null) {
			System.out.println(clusterID);
		}
		if (debugOut != null) {
			debugOut.append(']');
			System.out.println(debugOut.toString());
		}
		
		if (totalWeight == 0) {
			StringBuilder sb = new StringBuilder();
			sb.append("Ayee! totalWeight=0\n");
			
			for(int lmNum=0; lmNum<lms.length; ++lmNum) {
				LanguageModel lm = lms[lmNum];
				double weights[] = forest.getDecodingRuntime().getWeights(lmNum);
				
				int lmid = lm.getIdNum();
				
				BinaryTree<HistoryTreePayload> node = nodes[lmid];
				if (node == null) continue;
				int clusterid = node.getPayload().clusterid;
				
				double weight = 0;
				
				String backoffStr = "";
				
				if (node.getPayload().isBackoff) {
					backoffStr = " backoff (0)";
					if (forest.isBackoffLeavesUseGrandparent()) {
						// a backoff cluster, take the grandparent for interpolation
						BinaryTree<HistoryTreePayload> grandparent = node.getParent().getParent();

						weight = weights[grandparent.getPayload().clusterid];
						backoffStr = " backoff (gp)";
					}
				} else {
					weight = weights[clusterid];
				}
				
				sb.append(String.format("[%s@%d w=%f%s] ", lm.getId(), clusterid, weight, backoffStr));
			}
			System.err.println(sb.toString());
		}
		
		OnDiskCompactProbTree probTree = null;
		if (numTrees == 0) {
			return null;
		} else if (numTrees == 1) {
			probTree = (OnDiskCompactProbTree) probTrees[0].clone();
		} else {
			if (numTrees < treeWeights.length) {
				treeWeights = Arrays.copyOf(treeWeights, numTrees);
				probTrees = Arrays.copyOf(probTrees, numTrees);
			}
			probTree = OnDiskCompactProbTree.merge(probTrees, treeWeights);

			if (probTree != null && totalWeight != 1.0) {
				probTree.scale(1.0/totalWeight);
			}
		}
		
		return probTree;
	}
	
	public static TreeTrellisNode createTreeTrellis(int addedStarts) {
		
		TreeTrellisNode head = new TreeTrellisNode();
		if (addedStarts > 0) {
			return addStarts(head, addedStarts);
		}
		return head;
	}
	
	public static TreeTrellisNode addStarts(TreeTrellisNode head, int addedStarts) {
		Experiment experiment = Experiment.getInstance();
		FactorTupleDescription desc = experiment.getTupleDescription();
		
		long startTuple = desc.createStartTuple();
		BinaryPrefix startPrefix = experiment.getHiddenPrefix(startTuple & desc.getHiddenFactorsMask());
		
		TreeTrellisNode node = head;
		
		TrellisNodeItem item = null;
		
		while(addedStarts-- > 0) {
			node = node.appendNodeAndLock(startTuple & desc.getOvertFactorsMask());
			node.getPreviousNode().lock(1);

			if (!node.isDecoded()) {
				TrellisNodeItem newItem = new TrellisNodeItem(new ProbTree(startPrefix), 1.0, node.time);
				node.insertItem(newItem);
	
				node.setTotalProb(1.0);
				
				if (item != null) {
					item.addNextItem(newItem);
					
					newItem.addPrevItem(item);
				}
				item = newItem;
				node.finishDecoding();
			}
			node.unlock(2);
		}

		return node;
	}
	
	public SentenceContext createContext() {
		Experiment experiment = Experiment.getInstance();
		int order = forest.getOrder();
		
		SentenceContext ctx = new SentenceContext(order-1);
		//ctx.items = new SliceItem[Math.max(1, order-1)];
		//ctx.queues = new LinkQueue[Math.max(1, order-1)];
		//ctx.predictions = new BinaryTree[experiment.getNumLMs()];
		ctx.setDebug(debug);

		long startTuple = experiment.getTupleDescription().createStartTuple(); 
		BinaryPrefix startPrefix = experiment.getHiddenPrefix(startTuple);
		ctx.getTrellis().newSlice(startTuple);
		ProbTree startProbTree = new ProbTree(startPrefix);
		TrellisItem sliceItem = new TrellisItem(startProbTree, 1.0); 
		ctx.getCurrentSlice().insertItem(sliceItem);
		ctx.getCurrentSlice().curr2prev.put(sliceItem, null);
		
		for(int i=1; i<order-1; ++i) {
			ctx.getTrellis().newSlice(startTuple);
			TrellisSlice currentSlice = ctx.getCurrentSlice();
			
			TrellisItem newSliceItem = new TrellisItem(startProbTree, 1.0);
			currentSlice.insertItem(newSliceItem);
			ArrayList<TrellisItem> lst = new ArrayList<TrellisItem>(1);
			lst.add(sliceItem);
			currentSlice.curr2prev.put(newSliceItem, lst);
			
			lst = new ArrayList<TrellisItem>(1);
			lst.add(newSliceItem);
			currentSlice.prev2curr.put(sliceItem, lst);
			
			sliceItem = newSliceItem;
			currentSlice.getTotalProb();
		}
		ctx.setLastSliceTotalProb(1.0);
		return ctx;
	}

	private static final Comparator<TrellisItem> itemComparator = new Comparator<TrellisItem>() {
		@Override
		public int compare(TrellisItem arg0, TrellisItem arg1) {
			// reverse order
			return - (int) Math.signum(arg0.getProb() - arg1.getProb());
		}
	};
	
	private static final Comparator<TrellisNodeItem> newItemComparator = new Comparator<TrellisNodeItem>() {
		@Override
		public int compare(TrellisNodeItem o1, TrellisNodeItem o2) {
			return - (int) Math.signum(o1.getProb() - o2.getProb());
		}
	};
	
	private TimingData timingData = new TimingData(0, 0, 0, 0, 0);

	@SuppressWarnings("unchecked")
	void partition(DecodingContext context) {
		TreeTrellisNode currentNode = context.getCurrentNode();
		
		long partitionStartTime = Timing.nanoTime();
		int numLMs = Experiment.getInstance().getNumLMs();
		
		if (forest.getOrder() > 1) {
			               
			TrellisNodeItem items[] = currentNode.getPreviousNode().itemsArray();
			Arrays.sort(items, newItemComparator);
			double bestProb = items[0].getProb();
			
			ArrayDeque<TrellisNodeItem> agenda = new ArrayDeque<TrellisNodeItem>(items.length * 2);
			for(TrellisNodeItem item : items) {
				if (item.getProb() < bestProb * PRUNING_THRESHOLD) {
					//System.err.println("pruned!");
					break;
				}
				agenda.addFirst(item);
				context.setItemData(item, new ItemData(new BinaryTree[numLMs]));
			}
			
			while(!agenda.isEmpty()) {
				reallyNewPartition(context, agenda);
			}
		} else {
			BinaryTree<HistoryTreePayload> decodingPosition[] = new BinaryTree[numLMs];
			for(LanguageModel lm : forest.getModels()) {
				BinaryTree<HistoryTreePayload> historyTree = lm.getHistoryTree();
				decodingPosition[lm.getIdNum()] = historyTree;
				addCluster(context, lm.getIdNum(), historyTree);
			}
			context.addPrediction(decodingPosition, null);
		}
		
		long afterPartionTime = Timing.nanoTime();
		
		newGeneratePredictions(context);
		
		long afterPredictionsTime = Timing.nanoTime();

		//int point = 0;
		
		//System.out.printf("[%d] @%d logProb=%f\n", currentNode.time, ++point, currentNode.getLogProb());
		//System.out.printf("[%d] @%d logProb=%f\n", currentNode.time, ++point, currentNode.getLogProb());
		
		currentNode.rescale();
		
		//System.out.printf("[%d] @%d logProb=%f\n", currentNode.time, ++point, currentNode.getLogProb());
		
		if (debug > 0) {
			StringBuilder sb = new StringBuilder();
			debugContext(context, sb);
			System.out.print(sb.toString());
		}
		timingData.setTotalPartitionTime(timingData.getTotalPartitionTime()
				+ afterPartionTime - partitionStartTime);
		TimingData.totalPredictionTime.addAndGet(afterPredictionsTime - afterPartionTime);

	}
	
	public IdentityHashMap<TrellisNodeItem, Integer> ensurePrefixes(TreeTrellisNode node, BinaryPrefix prefixes[]) {
		IdentityHashMap<TrellisNodeItem, Integer> item2tag = new IdentityHashMap<TrellisNodeItem, Integer>(node.items.size());
		
		for(TrellisNodeItem item : node.itemsArray()) {
			for(int tag = 0; tag < prefixes.length; ++tag) {
				BinaryPrefix tagPrefix = prefixes[tag];
				if (tagPrefix == null) continue;
				ProbTree probTree = item.tree;

				double oldTreeProb = probTree.getTotalProb();

				probTree = item.tree.cut(tagPrefix);

				if (probTree == null) {
					// no true branch (was cut off during pruning)
					//falseItems.add(item);
					continue;
				} else if (probTree == item.tree) {
					// no false branch
					item2tag.put(item, Integer.valueOf(tag));
					break;
				} else {
					if (probTree.getTotalProb() < item.tree.getTotalProb() * PRUNING_THRESHOLD ||
							probTree.getTotalProb() * item.getPrevProb() < node.getTotalProb() * PRUNING_THRESHOLD) {
						// discard the cut off tree
						double probDiff = probTree.getTotalProb() * item.getPrevProb();
						if (probDiff > 0) {
							// instead of dropping the pruned probability add it back to the remaining part
							item.tree.scale(oldTreeProb / item.tree.getTotalProb());
						}

						continue;
					} else if (item.tree.getTotalProb() < probTree.getTotalProb() * PRUNING_THRESHOLD ||
							item.tree.getTotalProb() * item.getPrevProb() < node.getTotalProb() * PRUNING_THRESHOLD) {
						double probDiff = item.getPrevProb() * item.tree.getTotalProb(); 
						item.tree = probTree;

						if (probDiff > 0) {
							// instead of dropping the pruned probability add it back to the remaining part
							item.tree.scale(oldTreeProb / item.tree.getTotalProb());
						}
						item2tag.put(item, Integer.valueOf(tag));
						break;
					} else {
						TrellisNodeItem newItem = new TrellisNodeItem(probTree, item.getPrevProb(), item.time);
						item2tag.put(newItem, Integer.valueOf(tag));

						node.split(item, newItem);
					}
				}
			}
		}
		
		return item2tag;
	}
	
	void partition(SentenceContext ctx) {
		long realStartTime = Timing.nanoTime();
		
		TrellisSlice currentSlice = null;
		currentSlice = ctx.getSliceByOffset(-1);
		TrellisItem[] currentItems = currentSlice.getElements().toArray(new TrellisItem[0]);
		
		if (currentItems.length == 0) {
			System.err.printf("no elements at %d in %s\n", currentSlice.getTime(), ctx.getTrellis());
			return;
		}
		Arrays.sort(currentItems, itemComparator);
		
		//int itemsSize = Math.max(forest.getOrder()-1, 1);
		double bestProb = currentItems[0].getPrevProb() * currentItems[0].tree.getTotalProb();
		
		//ArrayList<LinkQueue> itemLists = new ArrayList<LinkQueue>(itemsSize);
		LinkedList<TrellisItem> currItems = new LinkedList<TrellisItem>();
		
		int itemNum = 0;
		for(TrellisItem currentItem : currentItems) {
			++itemNum;
			if (currentItem.getPrevProb() * currentItem.tree.getTotalProb() < bestProb * PRUNING_THRESHOLD) {
				//System.out.println("pruned!");
				break;
			}
			currItems.add(currentItem);
		}
		
		/*
		for(int i=2; i<forest.getOrder()-1; ++i) {
			// null out empty queues
			// items in the current slice (-1) have already null queue
			TrellisSlice s = ctx.getSliceByOffset(-i);
		}
		*/
		
		int numProbs = 0;
		long startTime = Timing.nanoTime();
		
		ctx.setCurrentRequests(new RequestBundle<Key,OnDiskCompactProbTree>(storage));
		
		final Context overtContext = new Context(forest.getOvertOrder());
		for(int i=0; i<overtContext.data.length; ++i) {
			overtContext.data[i] = ctx.getTrellis().getSliceByOffset(i + 1 - forest.getOvertOrder()).getOvertFactors();
		}

		// new decoding
		while(currItems.size() > 0) {
			TrellisItem headItem = currItems.remove();
			newPartition(ctx, overtContext, headItem, currItems);
		}
		
		long afterPartionTime = Timing.nanoTime();
		
		int numPredictions = currentSlice.getNext().getPredictions().getPredictions().size();
		
		generatePredictions(ctx, currentSlice.getNext());
		long afterPredictionsTime = Timing.nanoTime();
		
		// now merge the elements
/*		
		MutableInteger mergeIterationCount = new MutableInteger();
		int mergedCount = 0;

		for(int timeOffset = 0; timeOffset > 2 - forest.getHiddenOrder(); --timeOffset) {
			TrellisSlice nextSlice = ctx.getSliceByOffset(timeOffset);
			for(TrellisItem item : nextSlice.getElements()) {
				mergedCount += tryToMerge(nextSlice.getPreviousItems(item), mergeIterationCount);
			} 
			//nextSlice.checkLinks();
		}
		
		long afterMergeTime = Timing.nanoTime();
*/		
		{
			TrellisSlice nextSlice = currentSlice.getNext();
			double maxScale = nextSlice.getMaxScale();
			if (maxScale != 1.0) {
				nextSlice.scale(1.0 / maxScale);
				ctx.addLogScale(Math.log10(maxScale));
			}
		}
		if (debug > 0) {
			System.out.printf("[%d] : prep time %fs, %d iterations in %fs, %d predictions in %fs.\n", currentSlice.getNext().getTime(), 
					((double)(startTime - realStartTime))/1000000000, numProbs, ((double)(afterPartionTime - startTime))/1000000000,
					numPredictions, ((double)(afterPredictionsTime - afterPartionTime))/1000000000);
		}
		timingData.setTotalPrologTime(timingData.getTotalPrologTime() + startTime - realStartTime);
		timingData.setTotalPartitionTime(timingData.getTotalPartitionTime()
				+ afterPartionTime - startTime);
		TimingData.totalPredictionTime.addAndGet(afterPredictionsTime - afterPartionTime);
	}

	private static class SplitLinks<T> {
		public ArrayList<T> trueLinks;
		public ArrayList<T> falseLinks;
		
		public SplitLinks() {
			trueLinks = new ArrayList<T>(5);
			falseLinks = new ArrayList<T>(5);
		}
		
		public boolean isSplit() {
			return trueLinks.size() > 0 && falseLinks.size() > 0;
		}
		
		public boolean hasTrue() {
			return !trueLinks.isEmpty();
		}
		
		public boolean hasFalse() {
			return !falseLinks.isEmpty();
		}
	}
	
	public static boolean USE_COARSE_AND_FINE = false;
	public static double COARSE_THRESHOLD = 1e-5;
	
	private boolean useCoarse(SentenceContext ctx, TrellisItem headItem) {
		if (!USE_COARSE_AND_FINE) return false;
		double prob = headItem.getProb();
		return prob < COARSE_THRESHOLD * ctx.getLastSliceTotalProb();
	}
	
	private boolean useCoarse(DecodingContext ctx, TrellisNodeItem headItem) {
		if (!USE_COARSE_AND_FINE) return false;
		double prob = headItem.getProb();
		return prob < COARSE_THRESHOLD * ctx.getPrevNodeTotalProb();
	}
	
	private void addCluster(SentenceContext ctx, LanguageModel lm, Context overtContext, TrellisItem headItem, BinaryTree<HistoryTreePayload>[] predictions) {
		final int lmId = lm.getIdNum();
		BinaryTree<HistoryTreePayload> historyTree = headItem.getPosition(lmId);
		if (historyTree == null) {
			historyTree = lm.getHistoryTree();
		}

		HistoryTreePayload node = historyTree.getPayload();
		
		TrellisSlice newSlice = headItem.slice.getNext();
		
		predictions[lmId] = historyTree;
		
		{
			int requestClusterId = historyTree.getPayload().clusterid;
			if (node.isBackoff) {
				// request the grandparent
				requestClusterId = historyTree.getParent().getParent().getPayload().clusterid;
			}
			Key key = new Key(lmId, requestClusterId, newSlice.getOvertFactors());
			long start = Timing.nanoTime();
			ctx.getCurrentRequests().request(key);
			long end = Timing.nanoTime();
			if (Timing.TIMING) {
				TimingData.totalProbTreeRequestTime.addAndGet(end - start);
				TimingData.totalProbTreeRequestCount.incrementAndGet();
			}
		}
		return;

	}
	
	private void addCluster(DecodingContext context, int lmId, BinaryTree<HistoryTreePayload> node) {
		int requestClusterId = node.getPayload().clusterid;
		if (node.getPayload().isBackoff) {
			// request the grandparent
			requestClusterId = node.getParent().getParent().getPayload().clusterid;
		}
		Key key = new Key(lmId, requestClusterId, context.getFutureWord());

		long start = Timing.nanoTime();
		context.getCurrentRequests().request(key);
		long end = Timing.nanoTime();
		
		if (Timing.TIMING) {
			TimingData.totalProbTreeRequestTime.addAndGet(end - start);
			TimingData.totalProbTreeRequestCount.incrementAndGet();
		}
	}
	
	protected void reallyNewPartition(DecodingContext context, Deque<TrellisNodeItem> agenda) {
		
		TrellisNodeItem headItem = agenda.pollLast();
		if (headItem == null) return;
		
		Context overtContext = context.getOvertContext();
		ItemData headItemData = context.getItemData(headItem);
		
		//BinaryTree<HistoryTreePayload>[] predictions = new BinaryTree[Experiment.getInstance().getNumLMs()];

		for(int lmIdx=0; lmIdx<lms.length; ++lmIdx) {
			final LanguageModel lm = lms[lmIdx];
			final boolean isLastLM = lmIdx == lms.length - 1;
			final int lmId = lm.getIdNum();
			
			currentLM : while(true) {
				BinaryTree<HistoryTreePayload> historyTree = headItemData.getPosition(lmId);
				if (historyTree == null) {
					historyTree = lm.getHistoryTree();
				}
				headItemData.decodingPosition[lmId] = historyTree;
				
				HistoryTreePayload node = historyTree.getPayload();
				
				// we are when we've reached a leaf or the probability of reaching the state is small enough
				if (historyTree.isLeaf() || useCoarse(context, headItem)) {
					addCluster(context, lmId, historyTree);
					if (isLastLM) {
						context.addPrediction(headItemData.decodingPosition, headItem);
					}
					break currentLM;
				}
	
				Question question = node.question;
				final int questionOffset = - question.getTimeOffset() - 1;
				TreeTrellisNode theNode = context.getNodeByOffset(questionOffset).getPreviousNode();
				
				if (!question.isAboutHidden()) {
					// a question about overt factors does not split the context
					final boolean result;
					{
						long start = Timing.nanoTime();
						result = question.test(overtContext);
						long end = Timing.nanoTime();
						if (Timing.TIMING) {
							TimingData.totalQuestionTime.addAndGet(end - start);
							TimingData.totalQuestionCount.incrementAndGet();
						}
					}
					if (debug > 2) {
						System.out.printf("Question %s, head = %s, result=%s\n", question.toString(), headItem, result);
					}
					if (result) {
						headItemData.setPosition(lmId, historyTree.getRight());
					} else {
						headItemData.setPosition(lmId, historyTree.getLeft());
					}
				} else {
					// questions about hidden factors are more fun...

					Map<TrellisNodeItem,SplitLinks<TrellisNodeItem>> fwdItems = new IdentityHashMap<TrellisNodeItem,SplitLinks<TrellisNodeItem>>();
					if (questionOffset > 0) {
						RecursiveTreeTrellisIterator itemIterator = new RecursiveTreeTrellisIterator(headItem, questionOffset-1);
						for(; itemIterator.hasNext();) {
							fwdItems.put(itemIterator.next(), new SplitLinks<TrellisNodeItem>());
						}
					}
					LinkedList<TrellisNodeItem> currentItems = new LinkedList<TrellisNodeItem>();
					
					final boolean checkDupes = question.getTimeOffset() < -2;
					Map<TrellisNodeItem,TrellisNodeItem> _currentItems = checkDupes ? new IdentityHashMap<TrellisNodeItem,TrellisNodeItem>(100) : null;
					
					try {
						for(RecursiveTreeTrellisIterator itemIterator = new RecursiveTreeTrellisIterator(headItem, questionOffset); itemIterator.hasNext(); ) {
							TrellisNodeItem i = itemIterator.next();
							if (checkDupes) {
								if (_currentItems.containsKey(i)) continue;
								_currentItems.put(i, i);
							}
							currentItems.add(i);
						}
					} catch(NullPointerException e) {
						System.err.printf("Oops! headItem=%s, questionOffset=%d, context=%s, future=%s\n", 
								headItem, questionOffset, context.getOvertContext().toStringNoNull(), FactorTuple.toStringNoNull(context.getFutureWord()));
						e.printStackTrace();
					}
					if (checkDupes) {
						_currentItems = null;
					}
					
					/*
					if (debug > 1) {
						System.out.printf("checking prev links before hidden question, headItem = %s, nrItems = %d\n", 
								headItem, currentItems.size());
						headItem.checkPrevProb();
					}
					*/
					
					for(; !currentItems.isEmpty();) {
						TrellisNodeItem item = currentItems.remove();
		
						final Question.TestResult result;
						{
							long start = Timing.nanoTime();
							result = question.test(item.tree);
							long end = Timing.nanoTime();
							if (Timing.TIMING) {
								TimingData.totalQuestionTime.addAndGet(end - start);
								TimingData.totalQuestionCount.incrementAndGet();
							}
						}
						if (debug > 2) {
							System.out.printf("Question %s, head = %s, result=%s\n", question.toString(), headItem, result);
						}
						if (!result.isSplit()) {
							if (result.getResult()) {
								//trueItems.add(item);
								if (questionOffset > 0) {
									for(TrellisNodeItem fwd : item.getNextItems()) {
										SplitLinks<TrellisNodeItem> links = fwdItems.get(fwd);
										if (links != null) {
											links.trueLinks.add(item);
										}
									}
								} else {
									headItemData.setPosition(lmId, historyTree.getRight());
								}
							} else {
								//falseItems.add(item);
								if (questionOffset > 0) {
									for(TrellisNodeItem fwd : item.getNextItems()) {
										SplitLinks<TrellisNodeItem> links = fwdItems.get(fwd);
										if (links != null) {
											links.falseLinks.add(item);
										}
									}
								} else {
									headItemData.setPosition(lmId, historyTree.getLeft());
								}
							}
							continue;
						}
						
						//int index = items.indexOf(result.getItem());
						//TrellisItem sliceItem = (TrellisItem) result.getItem();
						ProbTree probTree = (ProbTree) result.getItem();
						
						if (debug > 1) {
							System.out.printf("splitting %s\n", item);
							//headItem.checkPrevProb();
						}
						
						// the interesting part: split the sliceItem
						//System.out.printf("old tree prob: %f\n", sliceItem.tree.getTreeProb());
						double oldTreeProb = probTree.getTotalProb();
						
						{
							long start = Timing.nanoTime();
							probTree = item.tree.cut(result.getPrefix());
							long end = Timing.nanoTime();
							if (Timing.TIMING) {
								TimingData.totalCuttingTime.addAndGet(end - start);
								TimingData.totalCuttingCount.incrementAndGet();
							}
						}
						if (probTree == null) {
							if (debug > 2) {
								System.out.println("no true branch");
								if (!ProbMath.approxEqual(oldTreeProb, item.tree.getTotalProb())) {
									System.out.printf("probTree was %g, now %g\n", oldTreeProb, item.tree.getTotalProb());
								}
							}
							// no true branch (was cut off during pruning)
							//falseItems.add(item);
							if (questionOffset > 0) {
								for(TrellisNodeItem fwd : item.getNextItems()) {
									SplitLinks<TrellisNodeItem> links = fwdItems.get(fwd);
									if (links != null) {
										links.falseLinks.add(item);
									}
								}
							} else {
								headItemData.setPosition(lmId, historyTree.getLeft());
							}
							continue;
						} else if (probTree == item.tree) {
							if (debug > 2) {
								System.out.println("no false branch");
								if (!ProbMath.approxEqual(oldTreeProb, item.tree.getTotalProb())) {
									System.out.printf("probTree was %g, now %g\n", oldTreeProb, probTree.getTotalProb());
								}
							}
							/*
							if (!ProbMath.approxEqual(oldTreeProb, sliceItem.tree.getTotalProb())) {
								// a negligible amount of probability
								sliceItem.slice.updateForwardProbabilities(sliceItem, probTree.getTotalProb() - oldTreeProb);
								//System.out.printf("probTree was %g, now %g\n", oldTreeProb, probTree.getTotalProb());
							}
							*/
							// no false branch
							//trueItems.add(item);
							if (questionOffset > 0) {
								for(TrellisNodeItem fwd : item.getNextItems()) {
									SplitLinks<TrellisNodeItem> links = fwdItems.get(fwd);
									if (links != null) {
										links.trueLinks.add(item);
									}
								}
							} else {
								headItemData.setPosition(lmId, historyTree.getRight());
							}
							continue;
						} else {
							if (debug > 2) {
								System.out.printf("new tree probs: %f and %f\n", probTree.getTotalProb(), item.tree.getTotalProb());
							}
							if (probTree.getTotalProb() < item.tree.getTotalProb() * PRUNING_THRESHOLD ||
									probTree.getTotalProb() * item.getPrevProb() < theNode.getTotalProb() * PRUNING_THRESHOLD) {
								// discard the cut off tree
								if (debug > 1) {
									System.out.printf("discarding split subtree %s (1): %e vs. %e\n", item, probTree.getTotalProb(), item.tree.getTotalProb());
								}
								double probDiff = probTree.getTotalProb() * item.getPrevProb();
								if (probDiff > 0) {
									//theNode.updateForwardProbabilities(item, -probDiff);
									// instead of dropping the pruned probability add it back to the remaining part
									item.tree.scale(oldTreeProb / item.tree.getTotalProb());
								}
		
								//falseItems.add(item);
								if (questionOffset > 0) {
									for(TrellisNodeItem fwd : item.getNextItems()) {
										SplitLinks<TrellisNodeItem> links = fwdItems.get(fwd);
										if (links != null) {
											links.falseLinks.add(item);
										}
									}
								} else {
									headItemData.setPosition(lmId, historyTree.getLeft());
								}
								continue;
								//partitionContext(itemLists, items, historyTree.getLeft(), predictions, scale, level+1);
							} else if (item.tree.getTotalProb() < probTree.getTotalProb() * PRUNING_THRESHOLD ||
									item.tree.getTotalProb() * item.getPrevProb() < theNode.getTotalProb() * PRUNING_THRESHOLD) {
								if (debug > 1) {
									System.out.printf("discarding split subtree %s (2): %e vs. %e\n", item, probTree.getTotalProb(), item.tree.getTotalProb());
								}
								double probDiff = item.getPrevProb() * item.tree.getTotalProb(); 
								item.tree = probTree;
								
								if (probDiff > 0) {
									//theNode.updateForwardProbabilities(item, -probDiff);
									// instead of dropping the pruned probability add it back to the remaining part
									item.tree.scale(oldTreeProb / item.tree.getTotalProb());
								}
								
								//trueItems.add(item);
								if (questionOffset > 0) {
									for(TrellisNodeItem fwd : item.getNextItems()) {
										SplitLinks<TrellisNodeItem> links = fwdItems.get(fwd);
										if (links != null) {
											links.trueLinks.add(item);
										}
									}
								} else {
									headItemData.setPosition(lmId, historyTree.getRight());
								}
								continue;
							} else {
								TrellisNodeItem newItem = new TrellisNodeItem(probTree, item.getPrevProb(), item.time);
								
								if (item.time != theNode.time) {
									System.out.print("");
								}
								theNode.split(item, newItem);
								
								//sliceItem.slice.split(item, newItem);
		
								if (debug > 1) {
									System.out.printf("cutting %s off %s\n", newItem, item);
								}
								//headItem.setPosition(lmId, historyTree.getLeft());
		
								//falseItems.add(item);
								if (questionOffset > 0) {
									for(TrellisNodeItem fwd : item.getNextItems()) {
										SplitLinks<TrellisNodeItem> links = fwdItems.get(fwd);
										if (links != null) {
											links.falseLinks.add(item);
											links.trueLinks.add(newItem);
										}
									}
								} else {
									agenda.add(newItem);
									ItemData newItemData = (ItemData) headItemData.clone();
									newItemData.setPosition(lmId, historyTree);
									context.setItemData(newItem, newItemData);
									//headItem.setPosition(lmId, historyTree.getRight());
								}
							}
						}
					} // itemIterator
					
					/*
					if (debug > 1) {
						System.out.printf("checking prev links after hidden question, headItem = %s\n", headItem);
						headItem.checkPrevProb();
					}
					*/
					
					if (questionOffset == 0) continue;
					
					boolean hasFalse = false;
					boolean hasTrue = false;
					
					for(SplitLinks<TrellisNodeItem> links : fwdItems.values()) {
						if (links.hasFalse()) hasFalse = true;
						if (links.hasTrue()) hasTrue = true;
						if (hasFalse && hasTrue) break;
					}
					
					if (!hasFalse) {
						headItemData.setPosition(lmId, historyTree.getRight());
					} else if (!hasTrue) {
						headItemData.setPosition(lmId, historyTree.getLeft());
					} else {
						
						long beforeFwdSplitting = Timing.nanoTime();
						int currentOffset = questionOffset - 1;
						while(currentOffset > 0) {
							TreeTrellisNode currentNode = context.getNodeByOffset(currentOffset).getPreviousNode();
							
							Map<TrellisNodeItem,SplitLinks<TrellisNodeItem>> newFwdItems = new IdentityHashMap<TrellisNodeItem,SplitLinks<TrellisNodeItem>>();
							RecursiveTreeTrellisIterator iter = new RecursiveTreeTrellisIterator(headItem, currentOffset-1);
							for(; iter.hasNext();) {
								newFwdItems.put(iter.next(), new SplitLinks<TrellisNodeItem>());
							}
		
							// copy items in the next slice that have both true and false links
							for(Map.Entry<TrellisNodeItem, SplitLinks<TrellisNodeItem>> entry : fwdItems.entrySet()) {
								TrellisNodeItem item = entry.getKey();
								SplitLinks<TrellisNodeItem> links = entry.getValue();
								
								if (links.isSplit()) {
									TrellisNodeItem newItem = (TrellisNodeItem) item.clone();
									currentNode.insertItem(newItem);
									// item.slice.insertItem(newItem);
									
									// copy links to the following slice if it exists
									if (item.getNextItems() != null) {
										//nextSlice.prev2curr.put(cutOff, (ArrayList<TrellisItem>)fwdLinks.clone());
										for(TrellisNodeItem i : item.getNextItems()) {
											newItem.addNextItem(i);
											i.addPrevItem(newItem);
										}
									}

									// newItem belongs to the "true" branch
									newItem.clearPrevItems();
									for(TrellisNodeItem i : links.trueLinks) {
										newItem.addPrevItem(i);
									}
									//newItem.prevItems = links.trueLinks;
									
									item.clearPrevItems();
									for(TrellisNodeItem i : links.falseLinks) {
										item.addPrevItem(i);
									}
									
									double prevTrueProb = 0;
									for(TrellisNodeItem prevTrueItem : links.trueLinks) {
										if (prevTrueItem.removeNextItem(item) == null) {
											if (debug > 1) {
												System.err.printf("can't find forwardLinks %s of %s\n", item, prevTrueItem);
											}											
										} else {
											prevTrueItem.addNextItem(newItem);
											prevTrueProb += prevTrueItem.getProb() * prevTrueItem.getPrevProb();
										}
									}
									newItem.setPrevProb(prevTrueProb);
									item.addPrevProb(-prevTrueProb);
									if (debug > 2) {
										System.out.printf("moved %g prevProb from %s to %s\n", prevTrueProb, newItem, item);
									}
									for(TrellisNodeItem fwd : item.getNextItems()) {
										SplitLinks<TrellisNodeItem> newLinks = newFwdItems.get(fwd);
										if (newLinks != null) {
											newLinks.falseLinks.add(item);
											newLinks.trueLinks.add(newItem);
										}
									}
									
								} else {
									for(TrellisNodeItem fwd : item.getNextItems()) {
										SplitLinks<TrellisNodeItem> newLinks = newFwdItems.get(fwd);
										if (newLinks != null) {
											if (links.hasFalse()) {
												newLinks.falseLinks.add(item);
											}
											if (links.hasTrue()) {
												newLinks.trueLinks.add(item);
											}
										}
									}
								}
							}					
							fwdItems = newFwdItems;
							--currentOffset;
						}
						long afterFwdSplitting = Timing.nanoTime();
						if (Timing.TIMING) {
							TimingData.totalFwdSplittingTime.addAndGet(afterFwdSplitting - beforeFwdSplitting);
						}
						/*
						if (debug > 1) {
							System.out.printf("checking prev links [point 2], headItem = %s\n", headItem);
							headItem.checkPrevProb();
						}
						*/
						
						// fwdItems should contain just one element: headItem
						assert(fwdItems.size() == 1);
						
						
						// copy items in the next slice that have both true and false links
						//for(Map.Entry<TrellisNodeItem, SplitLinks<TrellisNodeItem>> entry : fwdItems.entrySet()) 
						{
							TreeTrellisNode headNode = context.getCurrentNode().getPreviousNode();
							
							//TrellisNodeItem item = entry.getKey();
							SplitLinks<TrellisNodeItem> links = fwdItems.get(headItem);
							
							if (links.isSplit()) {
								TrellisNodeItem newItem = (TrellisNodeItem) headItem.clone();
								headNode.insertItem(newItem);
								ItemData newItemData = (ItemData) headItemData.clone();
								
								// copy links to the following slice if it exists
								if (headItem.getNextItems() != null) {
									for(TrellisNodeItem i : headItem.getNextItems()) {
										newItem.addNextItem(i);
										i.addPrevItem(newItem);
									}
								}

								// newItem belongs to the "true" branch
								newItem.clearPrevItems();
								for(TrellisNodeItem i : links.trueLinks) {
									newItem.addPrevItem(i);
								}
								//newItem.prevItems = links.trueLinks;
								
								headItem.clearPrevItems();
								for(TrellisNodeItem i : links.falseLinks) {
									headItem.addPrevItem(i);
								}

								double prevTrueProb = 0;
								//headNode.dumpNodePath("trellis-dump.dot", true);
								for(TrellisNodeItem prevTrueItem : links.trueLinks) {
									prevTrueItem.removeNextItem(headItem);
									prevTrueItem.addNextItem(newItem);
									//ArrayList<TrellisNodeItem> fwdLinks = prevTrueItem.nextItems;
									//int idx = fwdLinks.indexOf(headItem);
									//fwdLinks.set(idx, newItem);
									prevTrueProb += prevTrueItem.getProb() * prevTrueItem.getPrevProb();
								}
								newItem.setPrevProb(prevTrueProb);
								newItemData.setPosition(lmId, historyTree.getRight());
								
								headItem.addPrevProb(-prevTrueProb);
								headItemData.setPosition(lmId, historyTree.getLeft());
								
								agenda.add(newItem);
								context.setItemData(newItem, newItemData);
							} else if (!links.hasFalse()) {
								headItemData.setPosition(lmId, historyTree.getRight());
							} else {
								headItemData.setPosition(lmId, historyTree.getLeft());
							}
						}
		
					}

				}

				//break;
			}
				
		}

	}

	@SuppressWarnings("unchecked")
	protected void newPartition(SentenceContext ctx, Context overtContext, TrellisItem headItem, List<TrellisItem> agenda) {
		BinaryTree<HistoryTreePayload>[] predictions = new BinaryTree[Experiment.getInstance().getNumLMs()];
		
		//SliceItem headItem = agenda.remove(0);
		for(int lmIdx=0; lmIdx<lms.length; ++lmIdx) {
			final LanguageModel lm = lms[lmIdx];
			final boolean isLastLM = lmIdx == lms.length - 1;
			final int lmId = lm.getIdNum();
			
			currentLM : while(true) {
				BinaryTree<HistoryTreePayload> historyTree = headItem.getPosition(lmId);
				if (historyTree == null) {
					historyTree = lm.getHistoryTree();
				}
				
				HistoryTreePayload node = historyTree.getPayload();
				if (historyTree.isLeaf()) {
					addCluster(ctx, lm, overtContext, headItem, predictions);
					if (isLastLM) {
						headItem.slice.getNext().addPrediction(predictions.clone(), headItem);
					}
					break currentLM;
				}
	
				Question question = node.question;
				int questionOffset = - question.getTimeOffset() - 1;
				
				if (!question.isAboutHidden()) {
					// a question about overt factors does not split the context
					final boolean result;
					{
						long start = Timing.nanoTime();
						result = question.test(overtContext);
						long end = Timing.nanoTime();
						if (Timing.TIMING) {
							TimingData.totalQuestionTime.addAndGet(end - start);
							TimingData.totalQuestionCount.incrementAndGet();
						}
					}
					if (debug > 2) {
						System.out.printf("Question %s, head = %s, result=%s\n", question.toString(), headItem, result);
					}
					if (result) {
						headItem.setPosition(lmId, historyTree.getRight());
					} else {
						headItem.setPosition(lmId, historyTree.getLeft());
					}
				} else {
					// questions about hidden factors are more fun...
					HashMap<TrellisItem,SplitLinks<TrellisItem>> fwdItems = new HashMap<TrellisItem,SplitLinks<TrellisItem>>();
					if (questionOffset > 0) {
						RecursiveSliceItemIterator itemIterator = new RecursiveSliceItemIterator(headItem, questionOffset-1);
						for(; itemIterator.hasNext();) {
							fwdItems.put(itemIterator.next(), new SplitLinks<TrellisItem>());
						}
					}
					LinkedList<TrellisItem> currentItems = new LinkedList<TrellisItem>();
					
					final boolean checkDupes = question.getTimeOffset() < -2;
					Map<TrellisItem,TrellisItem> _currentItems = checkDupes ? new IdentityHashMap<TrellisItem,TrellisItem>(100) : null;
					
					for(RecursiveSliceItemIterator itemIterator = new RecursiveSliceItemIterator(headItem, questionOffset); itemIterator.hasNext(); ) {
						TrellisItem i = itemIterator.next();
						if (checkDupes) {
							if (_currentItems.containsKey(i)) continue;
							_currentItems.put(i, i);
						}
						currentItems.add(i);
					}
					if (checkDupes) {
						_currentItems = null;
					}
					
					if (debug > 1) {
						System.out.printf("checking prev links before hidden question, headItem = %s, nrItems = %d\n", 
								headItem, currentItems.size());
						headItem.checkPrevProb();
					}
					
					for(; !currentItems.isEmpty();) {
						TrellisItem item = currentItems.remove();
		
						final Question.TestResult result;
						{
							long start = Timing.nanoTime();
							result = question.test(item);
							long end = Timing.nanoTime();
							if (Timing.TIMING) {
								TimingData.totalQuestionTime.addAndGet(end - start);
								TimingData.totalQuestionCount.incrementAndGet();
							}
						}
						if (debug > 2) {
							System.out.printf("Question %s, head = %s, result=%s\n", question.toString(), headItem, result);
						}
						if (!result.isSplit()) {
							if (result.getResult()) {
								//trueItems.add(item);
								if (questionOffset > 0) {
									for(TrellisItem fwd : item.slice.getNext().prev2curr.get(item)) {
										SplitLinks<TrellisItem> links = fwdItems.get(fwd);
										if (links != null) {
											links.trueLinks.add(item);
										}
									}
								} else {
									headItem.setPosition(lmId, historyTree.getRight());
								}
							} else {
								//falseItems.add(item);
								if (questionOffset > 0) {
									for(TrellisItem fwd : item.slice.getNext().prev2curr.get(item)) {
										SplitLinks<TrellisItem> links = fwdItems.get(fwd);
										if (links != null) {
											links.falseLinks.add(item);
										}
									}
								} else {
									headItem.setPosition(lmId, historyTree.getLeft());
								}
							}
							continue;
						}
						
						if (useCoarse(ctx, headItem)) {
							// don't split small items
							addCluster(ctx, lm, overtContext, headItem, predictions);
							if (isLastLM) {
								headItem.slice.getNext().addPrediction(predictions.clone(), headItem);
							}
							break currentLM;
						}
						
						//int index = items.indexOf(result.getItem());
						TrellisItem sliceItem = (TrellisItem) result.getItem();
						
						if (debug > 1) {
							System.out.printf("splitting %s\n", sliceItem);
							sliceItem.checkPrevProb();
						}
						
						// the interesting part: split the sliceItem
						//System.out.printf("old tree prob: %f\n", sliceItem.tree.getTreeProb());
						double oldTreeProb = sliceItem.tree.getTotalProb();
						ProbTree probTree;
						{
							long start = Timing.nanoTime();
							probTree = sliceItem.tree.cut(result.getPrefix());
							long end = Timing.nanoTime();
							if (Timing.TIMING) {
								TimingData.totalCuttingTime.addAndGet(end - start);
								TimingData.totalCuttingCount.incrementAndGet();
							}
						}
						if (probTree == null) {
							if (debug > 2) {
								System.out.println("no true branch");
								if (!ProbMath.approxEqual(oldTreeProb, sliceItem.tree.getTotalProb())) {
									System.out.printf("probTree was %g, now %g\n", oldTreeProb, sliceItem.tree.getTotalProb());
								}
							}
							/*
							if (!ProbMath.approxEqual(oldTreeProb, sliceItem.tree.getTotalProb())) {
								// a negligible amount of probability
								sliceItem.slice.updateForwardProbabilities(sliceItem, sliceItem.tree.getTotalProb() - oldTreeProb);
								//System.out.printf("probTree was %g, now %g\n", oldTreeProb, sliceItem.tree.getTotalProb());
							}
							*/
							// no true branch (was cut off during pruning)
							//falseItems.add(item);
							if (questionOffset > 0) {
								for(TrellisItem fwd : item.slice.getNext().prev2curr.get(item)) {
									SplitLinks<TrellisItem> links = fwdItems.get(fwd);
									if (links != null) {
										links.falseLinks.add(item);
									}
								}
							} else {
								headItem.setPosition(lmId, historyTree.getLeft());
							}
							continue;
						} else if (probTree == sliceItem.tree) {
							if (debug > 2) {
								System.out.println("no false branch");
								if (!ProbMath.approxEqual(oldTreeProb, sliceItem.tree.getTotalProb())) {
									System.out.printf("probTree was %g, now %g\n", oldTreeProb, probTree.getTotalProb());
								}
							}
							/*
							if (!ProbMath.approxEqual(oldTreeProb, sliceItem.tree.getTotalProb())) {
								// a negligible amount of probability
								sliceItem.slice.updateForwardProbabilities(sliceItem, probTree.getTotalProb() - oldTreeProb);
								//System.out.printf("probTree was %g, now %g\n", oldTreeProb, probTree.getTotalProb());
							}
							*/
							// no false branch
							//trueItems.add(item);
							if (questionOffset > 0) {
								for(TrellisItem fwd : item.slice.getNext().prev2curr.get(item)) {
									SplitLinks<TrellisItem> links = fwdItems.get(fwd);
									if (links != null) {
										links.trueLinks.add(item);
									}
								}
							} else {
								headItem.setPosition(lmId, historyTree.getRight());
							}
							continue;
						} else {
							if (debug > 2) {
								System.out.printf("new tree probs: %f and %f\n", probTree.getTotalProb(), sliceItem.tree.getTotalProb());
							}
							if (probTree.getTotalProb() < sliceItem.tree.getTotalProb() * PRUNING_THRESHOLD ||
									probTree.getTotalProb() * sliceItem.getPrevProb() < sliceItem.slice.bestProb * PRUNING_THRESHOLD) {
								// discard the cut off tree
								if (debug > 1) {
									System.out.printf("discarding split subtree %s (1): %e vs. %e\n", sliceItem, probTree.getTotalProb(), sliceItem.tree.getTotalProb());
								}
								double probDiff = probTree.getTotalProb() * sliceItem.getPrevProb();
								if (probDiff > 0) {
									sliceItem.slice.updateForwardProbabilities(sliceItem, -probDiff);
								}
		
								//falseItems.add(item);
								if (questionOffset > 0) {
									for(TrellisItem fwd : item.slice.getNext().prev2curr.get(item)) {
										SplitLinks<TrellisItem> links = fwdItems.get(fwd);
										if (links != null) {
											links.falseLinks.add(item);
										}
									}
								} else {
									headItem.setPosition(lmId, historyTree.getLeft());
								}
								continue;
								//partitionContext(itemLists, items, historyTree.getLeft(), predictions, scale, level+1);
							} else if (sliceItem.tree.getTotalProb() < probTree.getTotalProb() * PRUNING_THRESHOLD ||
									sliceItem.tree.getTotalProb() * sliceItem.getPrevProb() < sliceItem.slice.bestProb * PRUNING_THRESHOLD) {
								if (debug > 1) {
									System.out.printf("discarding split subtree %s (2): %e vs. %e\n", sliceItem, probTree.getTotalProb(), sliceItem.tree.getTotalProb());
								}
								double probDiff = sliceItem.getPrevProb() * sliceItem.tree.getTotalProb(); 
								sliceItem.tree = probTree;
								
								if (probDiff > 0) {
									sliceItem.slice.updateForwardProbabilities(sliceItem, -probDiff);
								}
								
								//trueItems.add(item);
								if (questionOffset > 0) {
									for(TrellisItem fwd : item.slice.getNext().prev2curr.get(item)) {
										SplitLinks<TrellisItem> links = fwdItems.get(fwd);
										if (links != null) {
											links.trueLinks.add(item);
										}
									}
								} else {
									headItem.setPosition(lmId, historyTree.getRight());
								}
								continue;
							} else {
								TrellisItem newItem = new TrellisItem(probTree, item.getPrevProb(), 
										(ClusterId)sliceItem.clusterid.clone());
								sliceItem.slice.split(item, newItem);
		
								if (debug > 1) {
									System.out.printf("cutting %s off %s\n", newItem, item);
								}
								//headItem.setPosition(lmId, historyTree.getLeft());
		
								//falseItems.add(item);
								if (questionOffset > 0) {
									for(TrellisItem fwd : item.slice.getNext().prev2curr.get(item)) {
										SplitLinks<TrellisItem> links = fwdItems.get(fwd);
										if (links != null) {
											links.falseLinks.add(item);
											links.trueLinks.add(newItem);
										}
									}
								} else {
									agenda.add(newItem);
									newItem.setPosition(lmId, historyTree);
									//headItem.setPosition(lmId, historyTree.getRight());
								}
							}
						}
					} // itemIterator
					if (debug > 1) {
						System.out.printf("checking prev links after hidden question, headItem = %s\n", headItem);
						headItem.checkPrevProb();
					}
					
					if (questionOffset == 0) continue;
					
					boolean hasFalse = false;
					boolean hasTrue = false;
					
					for(SplitLinks<TrellisItem> links : fwdItems.values()) {
						if (links.hasFalse()) hasFalse = true;
						if (links.hasTrue()) hasTrue = true;
						if (hasFalse && hasTrue) break;
					}
					
					if (!hasFalse) {
						headItem.setPosition(lmId, historyTree.getRight());
					} else if (!hasTrue) {
						headItem.setPosition(lmId, historyTree.getLeft());
					} else {
						if (debug > 1) {
							System.out.printf("checking prev links [point 1], headItem = %s\n", headItem);
							headItem.checkPrevProb();
						}
	
						if (useCoarse(ctx, headItem)) {
							// don't split small items
							addCluster(ctx, lm, overtContext, headItem, predictions);
							if (isLastLM) {
								headItem.slice.getNext().addPrediction(predictions.clone(), headItem);
							}
							break currentLM;
						}
						
						long beforeFwdSplitting = Timing.nanoTime();
						int currentOffset = questionOffset - 1;
						while(currentOffset > 0) {
							HashMap<TrellisItem,SplitLinks<TrellisItem>> newFwdItems = new HashMap<TrellisItem,SplitLinks<TrellisItem>>();
							RecursiveSliceItemIterator iter = new RecursiveSliceItemIterator(headItem, currentOffset-1);
							for(; iter.hasNext();) {
								newFwdItems.put(iter.next(), new SplitLinks<TrellisItem>());
							}
		
							// copy items in the next slice that have both true and false links
							for(Map.Entry<TrellisItem, SplitLinks<TrellisItem>> entry : fwdItems.entrySet()) {
								TrellisItem item = entry.getKey();
								SplitLinks<TrellisItem> links = entry.getValue();
								
								if (links.isSplit()) {
									TrellisItem newItem = (TrellisItem) item.clone();
									item.slice.insertItem(newItem);
									
									// copy links to the following slice if it exists
									{
										TrellisSlice nextSlice = item.slice.getNext();
										if (nextSlice != null) {
											ArrayList<TrellisItem> fwdLinks = nextSlice.prev2curr.get(item);
											if (fwdLinks != null) {
												nextSlice.prev2curr.put(newItem, (ArrayList<TrellisItem>)fwdLinks.clone());
												for(TrellisItem i : fwdLinks) {
													nextSlice.curr2prev.get(i).add(newItem);
												}
											}
										}
									}
		
									// newItem belongs to the "true" branch
									item.slice.curr2prev.put(newItem, links.trueLinks);
									item.slice.curr2prev.put(item, links.falseLinks);
									
									double prevTrueProb = 0;
									for(TrellisItem prevTrueItem : links.trueLinks) {
										ArrayList<TrellisItem> fwdLinks = item.slice.prev2curr.get(prevTrueItem);
										int idx = fwdLinks.indexOf(item);
										if (idx == -1) {
											if (debug > 1) {
												System.err.printf("can't find forwardLinks %s of %s\n", item, prevTrueItem);
											}
										} else {
											fwdLinks.set(idx, newItem);
											prevTrueProb += prevTrueItem.getProb() * prevTrueItem.getPrevProb();
										}
									}
									newItem.setPrevProb(prevTrueProb);
									item.addPrevProb(-prevTrueProb);
									if (debug > 2) {
										System.out.printf("moved %g prevProb from %s to %s\n", prevTrueProb, newItem, item);
									}
									for(TrellisItem fwd : item.slice.getNext().prev2curr.get(item)) {
										SplitLinks<TrellisItem> newLinks = newFwdItems.get(fwd);
										if (newLinks != null) {
											newLinks.falseLinks.add(item);
											newLinks.trueLinks.add(newItem);
										}
									}
								} else {
									for(TrellisItem fwd : item.slice.getNext().prev2curr.get(item)) {
										SplitLinks<TrellisItem> newLinks = newFwdItems.get(fwd);
										if (newLinks != null) {
											if (links.hasFalse()) {
												newLinks.falseLinks.add(item);
											}
											if (links.hasTrue()) {
												newLinks.trueLinks.add(item);
											}
										}
									}
								}
							}					
							fwdItems = newFwdItems;
							--currentOffset;
						}
						long afterFwdSplitting = Timing.nanoTime();
						if (Timing.TIMING) {
							TimingData.totalFwdSplittingTime.addAndGet(afterFwdSplitting - beforeFwdSplitting);
						}
						if (debug > 1) {
							System.out.printf("checking prev links [point 2], headItem = %s\n", headItem);
							headItem.checkPrevProb();
						}
						
						// fwdItems should contain just one element: headItem
						assert(fwdItems.size() == 1);
						
						
						// copy items in the next slice that have both true and false links
						for(Map.Entry<TrellisItem, SplitLinks<TrellisItem>> entry : fwdItems.entrySet()) {
							TrellisItem item = entry.getKey();
							SplitLinks<TrellisItem> links = entry.getValue();
							
							if (links.isSplit()) {
								TrellisItem newItem = (TrellisItem) item.clone();
								item.slice.insertItem(newItem);
								
								// copy links to the following slice if it exists
								{
									TrellisSlice nextSlice = item.slice.getNext();
									if (nextSlice != null) {
										ArrayList<TrellisItem> fwdLinks = nextSlice.prev2curr.get(item);
										if (fwdLinks != null) {
											nextSlice.prev2curr.put(newItem, (ArrayList<TrellisItem>)fwdLinks.clone());
											for(TrellisItem i : fwdLinks) {
												nextSlice.curr2prev.get(i).add(newItem);
											}
										}
									}
								}
		
								// newItem belongs to the "true" branch
								item.slice.curr2prev.put(newItem, links.trueLinks);
								item.slice.curr2prev.put(item, links.falseLinks);
								
								double prevTrueProb = 0;
								for(TrellisItem prevTrueItem : links.trueLinks) {
									ArrayList<TrellisItem> fwdLinks = item.slice.prev2curr.get(prevTrueItem);
									int idx = fwdLinks.indexOf(item);
									fwdLinks.set(idx, newItem);
									prevTrueProb += prevTrueItem.getProb() * prevTrueItem.getPrevProb();
								}
								newItem.setPrevProb(prevTrueProb);
								newItem.setPosition(lmId, historyTree.getRight());
								
								item.addPrevProb(-prevTrueProb);
								item.setPosition(lmId, historyTree.getLeft());
								
								agenda.add(newItem);
							} else if (!links.hasFalse()) {
								item.setPosition(lmId, historyTree.getRight());
							} else {
								item.setPosition(lmId, historyTree.getLeft());
							}
						}
		
					}
				}
				//break;
			}
		}

	}
	
	public String getStatistics() {
		final long nano = 1000000000;
		StringBuilder sb = new StringBuilder(1000);
		sb.append(String.format("Prolog time: %.3fs\n", (double)timingData.getTotalPrologTime() / nano));
		sb.append(String.format("Partition time: %.3fs\n", (double)timingData.getTotalPartitionTime() / nano));
		sb.append(String.format("  Prep time: %.3fs\n", TimingData.totalPrePartitionTime.doubleValue() / nano));
		sb.append(String.format("  Questions: %d in %.3fs\n", TimingData.totalQuestionCount.get(), TimingData.totalQuestionTime.doubleValue() / nano));
		sb.append(String.format("  Cutting: %d in %.3fs\n", TimingData.totalCuttingCount.get(), TimingData.totalCuttingTime.doubleValue() / nano));
		sb.append(String.format("  Splitting: %d in %.3fs\n", TimingData.totalSplittingCount.get(), TimingData.totalSplittingTime.doubleValue() / nano));
		sb.append(String.format("  Requests: %d in %.3fs\n", TimingData.totalProbTreeRequestCount.get(), TimingData.totalProbTreeRequestTime.doubleValue() / nano));
		sb.append(String.format("  FwdSplit time:  %.3fs\n", TimingData.totalFwdSplittingTime.doubleValue() / nano));
		sb.append(String.format("Prediction time: %fs\n", TimingData.totalPredictionTime.doubleValue() / nano));
		sb.append(String.format("  including tree merging: %fs\n", (double)timingData.getTotalTreeMergingTime() / nano));
		sb.append(String.format("    merges: leafy %d in %fs, compact %d in %fs\n", 
			ProbTree.totalLeafyMergeCount, (double) ProbTree.totalLeafyMergeTime / nano,
			ProbTree.totalCompactMergeCount, (double) ProbTree.totalCompactMergeTime / nano));
		sb.append(String.format("    merges: num %d, cloning %fs, compactifying %fs\n",
				ProbTree.totalMergingCount, (double) ProbTree.totalCloningTime / nano,
				(double) ProbTree.totalCompactifyingTime / nano));
		sb.append(String.format("  including storage: %fs\n", (double)timingData.getTotalStorageTime() / nano));
		sb.append(String.format("Merge time: %fs\n", (double)timingData.getTotalMergeTime() / nano));
		//sb.append(storage.getStats());
		sb.append("Storage stats: " + storage.getStats());
		//sb.append('\n');
		return sb.toString();
	}

	public AbstractProbTreeStorage getStorage() {
		return storage;
	}

	public void setStorage(AbstractProbTreeStorage storage) {
		this.storage = storage;
	}

	public int getDebug() {
		return debug;
	}

	public ForestModel getForest() {
		return forest;
	}
	
}
